Yleinen lukukuntaseula

Matematiikassa yleinen lukukuntaseula (GNFS) on tehokkain tunnettu algoritmi suurten kokonaislukujen jakamiseen alkutekijöidensä tuloksi. Siltä kestää

${\displaystyle O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}n\right)^{1 \over 3}(\log n)^{2 \over 3}\right)\right)}$

askelta jakaa n-numeroinen luku tekijöihin. Algoritmi on yleisempi kuin erityinen lukukuntaseula: siinä missä jälkimmäinen voi jakaa vain tiettyjä lukuja tekijöihin, yleinen lukukuntaseula voi jakaa tekijöihin kaikki paitsi alkuluvun potensseja. Sana lukukuntaseula viittaa yleensä nimenomaan yleiseen lukukuntaseulaan.

Lukukuntaseulat (sekä erityinen että yleinen) voidaan ymmärtää laajennuksena yksinkertaisemmasta rationaaliseulasta. Rationaaliseulaa käytettäessä luvun n tekijöihin jakamiseen on välttämätöntä etsiä niin sanottuja sileitä kertalukua n olevia lukuja (eli lukuja, joiden alkutekijät ovat pieniä). Toisaalta näitä lukuja on vähän, joten rationaaliseula on varsin käyttökelvoton tekijöihinjakamisalgoritmi. Tosin siitä kehitetyt neliöseulat ovat tehokkaita koska ne toimivat noin ${\displaystyle {\sqrt {n}}}$ kokoisilla luvuilla – MPQS on edelleen nopein menetelmä noin 60–120-numeroisiin lukuihin, rajakohta riippuu toteutustavasta.

Yleinen lukukuntaseula sen sijaan vaatii lukujen etsimistä lukuun n^1/d saakka, missä d on jokin ykköstä suurempi kokonaisluku. Koska isot luvut ovat paljon pienemmällä todennäköisyydellä sileitä kuin pienet luvut, johtuu tästä yleisen lukukuntaseulan tehokkuus kokonaislukujen tekijöihinjakamisalgoritmina. Mutta saavuttaakseen tämän nopeuseron, on algoritmin suoritettava laskut lukukunnissa. Tuloksena saadaan melko monimutkainen algoritmi verrattuna rationaaliseulaan.